From 5af474dc783693897adbaf038074a52ca3c4da4c Mon Sep 17 00:00:00 2001 From: tsteven4 <13596209+tsteven4@users.noreply.github.com> Date: Mon, 8 Jul 2019 14:54:46 -0600 Subject: [PATCH] modify position filter algorithm. (#373) For routes and tracks, the algorithm is modified to only remove consecutive points until the distance limit is exceeded. This prevents simulataneous removal of points on an outgoing and return leg, which can lead to gross corruption of the route/track shape. A test case that demonstrates the problem with the previous algorithm is added. --- position.cc | 136 +++++++++----------- position.h | 17 ++- reference/track/position_track.gpx | 50 +++++++ reference/track/position_track_filtered.gpx | 27 ++++ testo.d/position.test | 4 + xmldoc/filters/position.xml | 6 +- 6 files changed, 158 insertions(+), 82 deletions(-) create mode 100644 reference/track/position_track.gpx create mode 100644 reference/track/position_track_filtered.gpx diff --git a/position.cc b/position.cc index 009e01577..95994fe6a 100644 --- a/position.cc +++ b/position.cc @@ -22,95 +22,97 @@ #include // for fabs #include // for strtod -#include // for foreach +#include // for QList +#include // for qAsConst, QAddConst<>::Type #include "defs.h" #include "filterdefs.h" -#include "grtcirc.h" // for RAD, gcdist, radtomiles +#include "grtcirc.h" // for RAD, gcdist, radtometers #include "position.h" #if FILTERS_ENABLED double PositionFilter::gc_distance(double lat1, double lon1, double lat2, double lon2) { - return gcdist( - RAD(lat1), - RAD(lon1), - RAD(lat2), - RAD(lon2) - ); + return radtometers(gcdist( + RAD(lat1), + RAD(lon1), + RAD(lat2), + RAD(lon2) + )); } /* tear through a waypoint queue, processing points by distance */ -void PositionFilter::position_runqueue(WaypointList* waypt_list, int nelems, int qtype) +void PositionFilter::position_runqueue(WaypointList* waypt_list, int qtype) { - double dist, diff_time; - int i = 0, anyitem; + QList qlist; - Waypoint** comp = (Waypoint**) xcalloc(nelems, sizeof(*comp)); - int* qlist = (int*) xcalloc(nelems, sizeof(*qlist)); - - foreach (Waypoint* waypointp, *waypt_list) { - comp[i] = waypointp; - qlist[i] = 0; - i++; + for (const auto waypointp : qAsConst(*waypt_list)) { + qlist.append(WptRecord(waypointp)); } + int nelems = qlist.size(); - for (i = 0 ; i < nelems ; i++) { - anyitem = 0; - - if (!qlist[i]) { - for (int j = i + 1 ; j < nelems ; j++) { - if (!qlist[j]) { - dist = gc_distance(comp[j]->latitude, - comp[j]->longitude, - comp[i]->latitude, - comp[i]->longitude); + for (int i = 0 ; i < nelems ; ++i) { + bool something_deleted = false; - /* convert radians to integer feet */ - dist = (int)(5280*radtomiles(dist)); - diff_time = fabs(waypt_time(comp[i]) - waypt_time(comp[j])); + if (!qlist.at(i).deleted) { + for (int j = i + 1 ; j < nelems ; ++j) { + if (!qlist.at(j).deleted) { + double dist = gc_distance(qlist.at(j).wpt->latitude, + qlist.at(j).wpt->longitude, + qlist.at(i).wpt->latitude, + qlist.at(i).wpt->longitude); if (dist <= pos_dist) { - if (check_time && diff_time >= max_diff_time) { - continue; + if (check_time) { + double diff_time = fabs(waypt_time(qlist.at(i).wpt) - waypt_time(qlist.at(j).wpt)); + if (diff_time >= max_diff_time) { + continue; + } } - qlist[j] = 1; + qlist[j].deleted = true; switch (qtype) { case wptdata: - waypt_del(comp[j]); - delete comp[j]; + waypt_del(qlist.at(j).wpt); + delete qlist.at(j).wpt; break; case trkdata: - track_del_wpt(cur_rte, comp[j]); - delete comp[j]; + track_del_wpt(cur_rte, qlist.at(j).wpt); + delete qlist.at(j).wpt; break; case rtedata: - route_del_wpt(cur_rte, comp[j]); - delete comp[j]; + route_del_wpt(cur_rte, qlist.at(j).wpt); + delete qlist.at(j).wpt; break; default: break; } - anyitem = 1; + something_deleted = true; + } else { + // Unlike waypoints, routes and tracks are ordered paths. + // Don't eliminate points from the return path when the + // route or track loops back on itself. + if ((qtype == trkdata) || (qtype == rtedata)) { + break; + } } } } - if (anyitem && !!purge_duplicates) { + if (something_deleted && (purge_duplicates != nullptr)) { switch (qtype) { case wptdata: - waypt_del(comp[i]); - delete comp[i]; + waypt_del(qlist.at(i).wpt); + delete qlist.at(i).wpt; break; case trkdata: - track_del_wpt(cur_rte, comp[i]); - delete comp[i]; + track_del_wpt(cur_rte, qlist.at(i).wpt); + delete qlist.at(i).wpt; break; case rtedata: - route_del_wpt(cur_rte, comp[i]); - delete comp[i]; + route_del_wpt(cur_rte, qlist.at(i).wpt); + delete qlist.at(i).wpt; break; default: break; @@ -119,25 +121,15 @@ void PositionFilter::position_runqueue(WaypointList* waypt_list, int nelems, int } } - if (comp) { - xfree(comp); - } - - if (qlist) { - xfree(qlist); - } } void PositionFilter::position_process_any_route(const route_head* rh, int type) { - int i = rh->rte_waypt_ct; - - if (i) { + if (rh->rte_waypt_ct != 0) { cur_rte = const_cast(rh); - position_runqueue(&cur_rte->waypoint_list, i, type); + position_runqueue(&cur_rte->waypoint_list, type); cur_rte = nullptr; } - } void PositionFilter::position_process_rte(const route_head* rh) @@ -155,10 +147,8 @@ void PositionFilter::process() RteHdFunctor position_process_rte_f(this, &PositionFilter::position_process_rte); RteHdFunctor position_process_trk_f(this, &PositionFilter::position_process_trk); - int i = waypt_count(); - - if (i) { - position_runqueue(global_waypoint_list, i, wptdata); + if (waypt_count() != 0) { + position_runqueue(global_waypoint_list, wptdata); } route_disp_all(position_process_rte_f, nullptr, nullptr); @@ -169,21 +159,21 @@ void PositionFilter::init() { char* fm; - pos_dist = 0; - max_diff_time = 0; - check_time = 0; + pos_dist = 0.0; + max_diff_time = 0.0; + check_time = false; - if (distopt) { + if (distopt != nullptr) { pos_dist = strtod(distopt, &fm); - if ((*fm == 'm') || (*fm == 'M')) { - /* distance is meters */ - pos_dist *= 3.2802; + if (!((*fm == 'm') || (*fm == 'M'))) { + /* distance is feet */ + pos_dist = FEET_TO_METERS(pos_dist); } } - if (timeopt) { - check_time = 1; + if (timeopt != nullptr) { + check_time = true; max_diff_time = strtod(timeopt, &fm); } } diff --git a/position.h b/position.h index e7eb69348..4637892d0 100644 --- a/position.h +++ b/position.h @@ -45,11 +45,7 @@ private: char* distopt = nullptr; char* timeopt = nullptr; char* purge_duplicates = nullptr; - int check_time; - - typedef struct { - double distance; - } extra_data; + bool check_time; arglist_t args[4] = { { @@ -68,8 +64,17 @@ private: ARG_TERMINATOR }; + class WptRecord + { + public: + Waypoint* wpt{nullptr}; + bool deleted{false}; + + explicit WptRecord(Waypoint* w) : wpt(w) {} + }; + double gc_distance(double lat1, double lon1, double lat2, double lon2); - void position_runqueue(WaypointList* waypt_list, int nelems, int qtype); + void position_runqueue(WaypointList* waypt_list, int qtype); void position_process_any_route(const route_head* rh, int type); void position_process_rte(const route_head* rh); void position_process_trk(const route_head* rh); diff --git a/reference/track/position_track.gpx b/reference/track/position_track.gpx new file mode 100644 index 000000000..5b8d5f3fb --- /dev/null +++ b/reference/track/position_track.gpx @@ -0,0 +1,50 @@ + + + + + + Untitled Path + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/reference/track/position_track_filtered.gpx b/reference/track/position_track_filtered.gpx new file mode 100644 index 000000000..f895c62d8 --- /dev/null +++ b/reference/track/position_track_filtered.gpx @@ -0,0 +1,27 @@ + + + + + + Untitled Path + + + + + + + + + + + + + + + + + + + + + diff --git a/testo.d/position.test b/testo.d/position.test index 2669d8d77..bd59ae995 100644 --- a/testo.d/position.test +++ b/testo.d/position.test @@ -8,3 +8,7 @@ gpsbabel -i geo -f ${REFERENCE}/../geocaching.loc -o csv -F ${TMPDIR}/filterpos. gpsbabel -i geo -f ${REFERENCE}/../geocaching.loc -f ${REFERENCE}/../geocaching.loc -x position,distance=5f \ -o csv -F ${TMPDIR}/filterpos.csv2 sort_and_compare ${TMPDIR}/filterpos.csv1 ${TMPDIR}/filterpos.csv2 + +# check a track that loops back with a return leg adjacent to an outgoing leg. +gpsbabel -i gpx -f reference/track/position_track.gpx -x position,distance=12m -o gpx -F ${TMPDIR}/position_track_filtered.gpx +compare ${REFERENCE}/track/position_track_filtered.gpx ${TMPDIR}/position_track_filtered.gpx diff --git a/xmldoc/filters/position.xml b/xmldoc/filters/position.xml index 01df222c7..c6b957179 100644 --- a/xmldoc/filters/position.xml +++ b/xmldoc/filters/position.xml @@ -1,7 +1,7 @@ -This filter removes points based on their proximity to each other. A -point is removed if it is within the specified distance of a point that -has come before. +This filter removes points based on their proximity to each other. +For waypoints a point is removed if it is within the specified distance of a preceeding point. +For routes and tracks consecutive points are removed until the distance between the bracketing points is greater than the specified distance. -- 2.30.2